package com.leetcode.weicl.problems.no224;

import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/*
 * Problems No 224 
 * Basic Calculator
 * 
Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
Note: Do not use the eval built-in library function.
  
 * 
 * 思路：
 * 没有乘法除法。用计算数和操作符堆栈，实现括号优先级即可。
 */
public class Solution {
	
	Pattern p = Pattern.compile("([\\d]+|[+-]|[()])");
	
	// 转变为三元计算二叉树
	public int translate(String s) {
		Matcher m = p.matcher(s);
		
//		TrippleNode current = null;
		
		Stack<String> stack = new Stack<String>();
		Stack<Integer> operate = new Stack<Integer>();
		operate.push(1);
		
		while(m.find()) {
			String token = m.group();
//			System.out.println(token);
			
			if ("(".equals(token)) {
				stack.push(token);
				operate.push(1);
			} else if (")".equals(token)) {
				// pop up and calculate
				
				int tmp = 0;
				
				String top = null;
				while( !stack.isEmpty()) {
					top = stack.pop();
					if ("(".equals(top)) {
						break;
					}
					Integer value = Integer.parseInt(top);
					
					tmp += value * operate.pop();
				}
				
				stack.push(Integer.toString(tmp));
			} else if ("+".equals(token)) {
				operate.push(1);
			} else if ("-".equals(token)) {
				operate.push(-1);
			} else {
				// number
				stack.push(token);
			}
			
		}

		System.out.println(stack);
		
		int tmp = 0;
		
		String top = null;
		while( !stack.isEmpty()) {
			top = stack.pop();
			Integer value = Integer.parseInt(top);
			
			tmp += value * operate.pop();
		}
		
		
		return tmp;
	}
	
    public int calculate(String s) {
        int rt = 0;
        rt = translate(s);
        
    	return rt;
    }
    
    public static void main(String[] args) {
	    Solution s = new Solution();
	    String input = "";
	    
	    System.out.println("======================");
	    input = "0";
	    System.out.println("input: "+input);
	    System.out.println(s.calculate(input));
	    
	    
	    System.out.println("======================");
	    input = " 2-1 + 2 ";
	    System.out.println("input: "+input);
	    System.out.println(s.calculate(input));
	    
	    System.out.println("======================");
	    input = "(1+(4+5+2)-3)+(6+8)";
	    System.out.println("input: "+input);
	    System.out.println(s.calculate(input));
	    
	    System.out.println("======================");
	    input = "2-(5-6)";
	    System.out.println("input: "+input);
	    System.out.println(s.calculate(input));
    }
}